#include "LinkTree.h"
#include <iostream>

TreeNode::TreeNode(const ElementType &element)
{
    data = element;
    parent = nextSbling = FirstChild = nullptr;
    
}


void TreeNode::Connect(TreeNode *node)
{
    if(node == nullptr)
        return;
    this->parent = node;
    this->nextSbling = node->FirstChild;
    node->FirstChild = this;
}

void TreeNode::Disconnect(TreeNode *node)
{
    if(node == nullptr && this->parent != node)
        return;
    
    TreeNode *travelPoint = node->FirstChild;
    if(this == node->FirstChild)
        node->FirstChild = this->nextSbling;
    else
    {
        while(travelPoint->nextSbling != nullptr)
        {
            if(travelPoint->nextSbling == this)
            {
                travelPoint->nextSbling = this->nextSbling;
                break;
            }
            travelPoint = travelPoint->nextSbling;
        }
    }
    this->parent = this->nextSbling = nullptr;
}

LinkTree::LinkTree()
{
    root = new TreeNode(nullptr);
    Print = nullptr;
    Compare = nullptr;
    Copy = nullptr;
    Free = nullptr;
}

LinkTree::~LinkTree()
{
    FreeNode(root);
}

void LinkTree::show()
{
    show(root,-1);
}

DoubleLinkList LinkTree::FindByElement(const ElementType &element)
{
    DoubleLinkList list;
    FindNode(root,element,list);
    return list;
}

int LinkTree::GetTreeHight()
{
   return GetTreeHight(root) - 1;
}

int LinkTree::Size()
{
    int count = 0;
    GetNodeCount(root,count);
    return count - 1;
}

int LinkTree::LeafSize()
{
    int count = 0;
    GetLeafNode(root,count);
    return count;
}

void LinkTree::GetLeafNode(TreeNode *node, int &conut)
{
    if(node == nullptr)
    {
        return;
    }
    if(node->FirstChild == nullptr)
        conut++;
    GetLeafNode(node->FirstChild,conut);
    GetLeafNode(node->nextSbling,conut);
}

void LinkTree::GetNodeCount(TreeNode *node, int &conut)
{
    if(node == nullptr)
        return;
    conut++;
    GetNodeCount(node->FirstChild,conut);
    GetNodeCount(node->nextSbling,conut);
}


int LinkTree::GetTreeHight(TreeNode *node)
{
    if(node == nullptr)
        return 0;
    //return (GetTreeHight(node->FirstChild) > GetTreeHight(node->nextSbling) ? GetTreeHight(node->FirstChild) : GetTreeHight(node->nextSbling) + 1);
    int MaxHight = 0;
    TreeNode* travelPoint = node->FirstChild;
    while(travelPoint != nullptr)
    {
        int NodeHeight = GetTreeHight(travelPoint);
        MaxHight = MaxHight > NodeHeight ? MaxHight : NodeHeight;
        travelPoint = travelPoint->nextSbling;
    }
    return MaxHight + 1;
}

void LinkTree::FindNode(TreeNode *node, const ElementType &element, DoubleLinkList &list)
{
        if(node == nullptr)
            return;
        if(node != root && Compare(node->data,element) == 0 )
            list.InsertTail(node);
        FindNode(node->FirstChild,element,list);
        FindNode(node->nextSbling,element,list);
}

void LinkTree::show(TreeNode *node, int deepth)
{
    if(node == nullptr)
        return;
    if(node->parent != nullptr) //不是根节点才打印
    {
        if(deepth > 0)
        {
            for(int i = 0;i < deepth - 1;i++)
                std::cout<<"     ";
            if(node->nextSbling)
                std::cout<<" ├── " ;
            else
                std::cout<<" └── " ;
        }
        //std::cout<<(long)node->data<<std::endl;//存放数字时
        if(!Print)
            std::cout<<(char *)node->data<<std::endl;//存放字符串时
        else
            Print(node->data);
    }
    //深度优先遍历
    // show(node->FirstChild);
    // show(node->nextSbling);

    
    show(node->FirstChild,deepth + 1);
    show(node->nextSbling,deepth);
}

void LinkTree::FreeNode(TreeNode *node)
{
    if(node == nullptr)
        return;
    
    FreeNode(node->FirstChild);
    FreeNode(node->nextSbling);
    delete node;
}
